package com.ctwom.algorithm.questions.Csort;

/**
 * 给定一个整型数组arr，返回排序后相邻两数的最大差值
 * arr = [9,3,1,10]。如果排序，结果为[1,3,9,10]，9和3的差为最大差值，故返回6。
 * arr = [5,5,5,5]。返回0。
 * [要求]
 * 时间复杂度为O(n)O(n),空间复杂度为O(n)O(n)
 */
public class GetSortResultMaxDiffer {
    public static void main(String[] args) {
        int[] arr1 = {9, 3, 1, 10};
        int[] arr2 = {5, 5, 5, 5};
        System.out.println(getSortResultMaxDiffer(arr1));
        System.out.println(getSortResultMaxDiffer(arr2));
    }

    /**
     * 我的想法是使用选择排序，每次找到每次遍历de最小值，然后减去前一个值确定区间差值比较大小，保留最大的那个
     * 选择排序的时间复杂度是N^2，直接定位数组的前一位时间复杂度是1，需要一个maxDiffer变量，空间复杂度应该是1吧
     *
     * @param arr
     * @return
     */
    public static int getSortResultMaxDiffer(int[] arr) {
        int differ = 0;
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < min) {
                    int tmp = arr[j];
                    arr[j] = min;
                    min = tmp;
                }
            }
            arr[i] = min;
            if (i > 0 && (arr[i] - arr[i - 1]) > differ) {
                differ = arr[i] - arr[i - 1];
            }
        }
        return differ;
    }
}
